/*
实验12-3 逆序对
分数 35
作者 曹鹏
单位 Google

给定一个 1 到 n 的排列，我们已经学会了如何统计其中逆序对的个数。如果将其中一段连续子列逆转，又会有多少个逆序对呢？
例如给定序列 { 2, 1, 3 }中有 1 个逆序对；将后 2 个数字逆转后得到 { 2, 3, 1 }，就有 2 个逆序对了。
输入格式：

输入首先在一行中给出一个正整数 n（≤103），随后一行给出 1 到 n 的一个排列 { a0​，……，an−1​ }。数字间以空格分隔。
输出格式：

对于每一对下标 0≤i≤j<n，计算逆转了从 ai​ 到 aj​ 的元素后，序列中逆序对的个数。在一行中输出这 n(n+1)/2 个整数，按照 i 优先的顺序。即：前 n 个数字对应逆转了 {a0​，a0​}、{a0​，a1​}、……、{a0​，……，an−1​} 的结果；下面 n−1 个数字对应逆转了 {a1​，a1​}、{a1​，a2​}、……、{a1​，……，an−1​} 的结果；以此类推。
一行中的数字间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：

3
2 1 3

输出样例：

1 0 2 1 2 1

*/

/*
    预处理逆序对：

        使用树状数组（Fenwick Tree）计算原始数组的逆序对数量。

        同时，预处理出每个子列的逆序对数量。

    动态规划计算逆转后的逆序对：

        定义 dp[i][j] 表示逆转子列 [i, j] 后的逆序对数量。

        通过动态规划递推公式，计算每个子列逆转后的逆序对变化。

    利用滑动窗口的思想：

        对于每个子列逆转操作，利用预处理的信息，快速计算逆转后的逆序对数量。
*/

#include <iostream>
#include <vector>
using namespace std;

// 树状数组（Fenwick Tree）用于计算逆序对
class FenwickTree {
private:
    vector<int> tree;
    int n;

public:
    FenwickTree(int size) : n(size), tree(size + 1, 0) {}

    void update(int index, int value) {
        while (index <= n) {
            tree[index] += value;
            index += index & -index;
        }
    }

    int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= index & -index;
        }
        return sum;
    }
};

// 计算原始数组的逆序对数量
int countInversions(vector<int>& arr) {
    int n = arr.size();
    FenwickTree ft(n);
    int invCount = 0;
    for (int i = n - 1; i >= 0; i--) {
        invCount += ft.query(arr[i] - 1);
        ft.update(arr[i], 1);
    }
    return invCount;
}

// 动态规划计算所有子列逆转后的逆序对数量
vector<vector<int>> calculateInversionsAfterReverse(vector<int>& arr, int originalInversions) {
    int n = arr.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));

    // 预处理每个子列的逆序对数量
    for (int i = 0; i < n; i++) {
        FenwickTree ft(n);
        int invCount = 0;
        for (int j = i; j < n; j++) {
            invCount += ft.query(n) - ft.query(arr[j]);
            ft.update(arr[j], 1);
            dp[i][j] = invCount;
        }
    }

    // 计算逆转后的逆序对数量
    vector<vector<int>> result(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // 逆转子列 [i, j] 后的逆序对数量
            int internalInversions = dp[i][j];
            int newInternalInversions = (j - i + 1) * (j - i) / 2 - internalInversions;
            int externalInversions = originalInversions - internalInversions;
            result[i][j] = externalInversions + newInternalInversions;
        }
    }

    return result;
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int originalInversions = countInversions(arr);
    vector<vector<int>> result = calculateInversionsAfterReverse(arr, originalInversions);

    // 输出结果
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (i > 0 || j > 0) {
                cout << " ";
            }
            cout << result[i][j];
        }
    }
    cout << endl;

    return 0;
}